package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC187 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
         * @param 此题目参考了别人代码
         * 非常精妙的位运算和hash表应用
         * 可以借鉴思想，多多学习
         * @return:
         */
    class Solution {
        public List<String> findRepeatedDnaSequences(String s) {
            int len = s.length();
            if (len == 0 || len < 10) return new ArrayList<>();

            Set<String> res = new HashSet<>();
            Set<Integer> seenHash = new HashSet<>();
            char[] map = new char[26];
            map['A' - 'A'] = 0;
            map['C' - 'A'] = 1;
            map['G' - 'A'] = 2;
            map['T' - 'A'] = 3;
            int key = 0;
            char[] arr = s.toCharArray();

            //初始化key
            for (int i = 0; i < 10; i++) {
                key = key << 2 | map[arr[i] - 'A'];
            }

            seenHash.add(key);
            for (int i = 10; i < len; i++) {
                key <<= 2;
                key |= map[arr[i] - 'A'];
                key &= 0xfffff;

                if (seenHash.contains(key)) res.add(s.substring(i - 9, i + 1));
                else seenHash.add(key);
            }

            return new ArrayList<>(res);
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC187 an = new LC187();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
